It has been desired for navigation devices to accurately indicate the current state of roads, facilities, and the like of which map data used constantly changes. Therefore, it has been necessary to frequently update the map data. However, in conventional methods of providing map data recorded on a recording medium such as a DVD or CD, of performing a rewrite of map data in a hard disk by a dealer, and the like, a frequent update of map data has been difficult in terms of cost, time, and the like required for the update of map data. Accordingly, technology in which update data formed of update differential information of map data is provided from a server device to a navigation device, and a differential update of the map data stored in a recording medium such as a hard disk is performed by the navigation device using the update data has been known (for example, see Japanese Patent Application Publication No. JP-A-2004-178248). The navigation device performs various navigation processes such as a map display, a route search, and a route guidance using current position information acquired by a global positioning system (GPS) reception device or the like and the map data.